This invention relates to a method for analyzing array summaries without approximation for a loop containing a loop exit statement.
Parallel compilers execute a variety of transformations for parallelization of programs to improve the execution performance of the programs. The transformations for parallelization are primarily applied to loops. Arbitrary transformations for parallelization are not applicable to the loops, but it must be determined which transformations for parallelization are applicable.
The nucleus of determining whether transformations for parallelization are applicable is reference analysis of data within a loop. Data referenced within a loop include scalar variables and arrays. Each scalar variable always references the same memory area. In contrast to this, in the case of arrays, since different memory areas are referenced depending on the values of subscripts, it is necessary to analyze how which part of which array is referenced within a loop.
Accordingly, for parallel compilers to determine whether transformations for parallelization are applicable, an array summary analysis is developed to analyze the parts of each array referenced within a loop and the characteristics of the references. The array summary analysis is shown in M. Hall, B. Murphy, S. Amarasinghe, S. Liao, M. Lam, "Interprocedural analysis for parallelization, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing", Springer-Verlag, August 1995.
A program example in FIG. 4 will be used to describe an array summary analysis for determining whether transformations for parallelization called array privatization are applicable to an array A. The array summary analysis analyzes array reference to obtain an array summary in FIG. 8 in a bottom-up fashion from the innermost loop toward outer loops while tracing the program in the reverse of program execution order.
In FIG. 8, R denotes a statement, a loop body, a loop, and other program parts. The loop body refers to all statements within a loop; for example, the body of a loop L2 in FIG. 4 is only a statement S2. The loop body of a loop L is hereinafter represented as L(body). The array summary of a loop body is an array summary for one iteration of the loop and the array summary of a loop is an array summary for all iterations of the loop.
An array summary of a statement S2 becomes as shown in FIG. 9 (a). Since the loop L2 contains only the statement S2, the array summary of the loop L2 body is the array summary itself of S2 and becomes as shown in FIG. 9 (b). By eliminating the loop control variable K of loop L2 from the array summary of the loop L2 body by using a variable elimination method such as the Fourier-Motzkin variable elimination method, the array summary of the loop L2 becomes as shown in FIG. 9 (c). By performing the same processing for a statement S1 and a loop L1, the array summary of the loop L1 becomes as shown in FIG. 9 (d). Next, the array summary of loop L0 body is obtained as shown in FIG. 9 (e) from the array summaries of the loops L1 and L2.
In FIG. 9 (e), since ExposedRead of an array A becomes a null set in the loop L0 body, it is appreciated that all parts of the array from which values are read at each iteration of L0 have already been preset to values within the iteration. Hence, it is appreciated that, at each iteration of the loop L0, the values of array elements set in other iterations would not be read. Accordingly, by preparing a different array TA(1:N) for a different iteration of the loop L0 as substitution of the array A, it is appreciated that the iterations of the loop L0 can be executed independently of each other. The transformation of thus allocating arrays to memory areas independent of each other for each iteration is called array privatization.
Since array privatization allows the iterations of the loop L0 to be executed independently, parallelization can be implemented as shown in FIG. 5. DOALL indicates the beginning of a parallelization loop. A statement SO indicates that the memory area of array TA (1:N) is allocated individually for each iteration of a loop.
The above-described prior art states that an array summary analysis should be conducted with approximation when loop exit exists within a loop. However, no specific approximation method was described in the above-described prior art.
It is generally known that a set that may be referenced can be approximated with a set containing the actual set, while a set that must be referenced can be approximated with a set contained in the actual set. Therefore, an array summary analysis could also be conducted for a loop containing loop exit if, of array summaries for the loop, a set of parts of the array to which values may be written, a set of parts of the array from which values may be read, and a set of parts of the array from which values may be read before a value is written are approximated with array summaries without loop exit, while a set of parts of the array to which values must be written is approximated with a null set.
Thus, a method for conducting an array summary analysis for a loop containing loop exit is possible by expanding the prior art.
However, there was a problem in the above-mentioned expansion of the prior art in that analysis accuracy is degraded by approximation, and transformations for parallelization may be determined to be inapplicable although actually applicable.
For example, since a loop L1 contains loop exit in a program in FIG. 6, a set MustWrite (L1) of parts of an array to which values must be written in the loop L1 is approximated with a null set. For this reason, as shown in FIG. 10, a set [ExposedRead(L0 (body))] of parts of an array from which values may be read before a value is written at each iteration of the loop L0 body does not become a null set and it could not be determined that the array A can be privatized in the loop L0. Consequently, the loop L0 could not be parallelized.